Word Break
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
You're given a strip of text and a supply list of reusable text fragments.
Decide whether you can rebuild the strip end to end by placing fragments from the supply list one after another, in order, with no extra characters left over and no gaps. You can reuse any fragment as many times as you like.
Input: s = "redbluered", words = ["red", "blue"]
Output: True
Place "red", then "blue", then "red" again. That lines up exactly with the strip, reusing "red" twice.
Input: s = "aaaab", words = ["aa", "aaa"]
Output: False
Every fragment is made only of the letter "a", so there's no way to end the strip on a "b" no matter how you combine them.
Input: s = "xyz", words = ["xy", "yz"]
Output: False
Placing "xy" first covers "xy", but leaves just "z" over, which matches neither fragment on its own. Placing "yz" first doesn't even line up with the start of the strip.
Input: s = "", words = ["a", "b"]
Output: True
An empty strip is already complete before you place a single fragment.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.